#include "mySearch.h"
#include <iostream>
#include <string>


using namespace std;

SSTable::SSTable()
{
    length = 0;
    origin = NULL;
}

SSTable::SSTable(int l,int* o)
{
    length = l;
    origin = new int[l];
    for(int i = 0; i < l; i ++){
        origin[i] = o[i];
    }
}

SSTable::~SSTable() = default;

int SSTable::getLength()
{
    return length;
}

int* SSTable::getOrigin()
{
    return origin;
}

void SSTable::setLength(int l)
{
    length = l;
}

void SSTable::setOrigin(int* o)
{
    if(origin){
        delete [] origin;
    }
    origin = o;
}

int SSTable::binSearch(int val)
{
    int a = 0, b = length - 1;
    while(a != b){
        int c = origin[(a + b) / 2];
        if(val == c) return (a + b) / 2;
        if(val < c){
            b = ((a + b) / 2) - 1;
            continue;
        }
        else{
            a = ((a + b) / 2) + 1;
            continue;
        }
    }
    return (val == origin[a]) ? a : -1;
}

BSTreeNode::BSTreeNode()
{
    data = 0;
    lchild = NULL;
    rchild = NULL;
}

BSTreeNode::BSTreeNode(int d)
{
    data = d;
    lchild = NULL;
    rchild = NULL;
}

BSTreeNode::BSTreeNode(int d, BSTreeNode* l, BSTreeNode* r)
{
    data = d;
    lchild = l;
    rchild = r;
}

BSTreeNode::~BSTreeNode() = default;

int BSTreeNode::getData()
{
    return data;
}

BSTreeNode* BSTreeNode::getLChild()
{
    return lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
    return rchild;
}

void BSTreeNode::setData(int d)
{
    data = d;
}

void BSTreeNode::setLChild(BSTreeNode* l)
{
    lchild = l;
}

void BSTreeNode::setRChild(BSTreeNode* r)
{
    rchild = r;
}

BSTree::BSTree()
{
    num = 0;
    root = NULL;
}

BSTree::BSTree(int n, int* data)
{
    num = n;
    root = new BSTreeNode;
    root -> setData(data[0]);
    for(int i = 1; i < n; i ++){
        BSTreeNode* p = new BSTreeNode;
        p -> setData(data[i]);
        BSTreeNode* q = root;
        while(q){
            if(data[i] < q -> getData( )){
                if(q -> getLChild()){
                    q = q -> getLChild();
                }
                else{
                    q -> setLChild(p);
                    break;
                }
            }
            else{
                if(q -> getRChild()){
                    q = q -> getRChild();
                }
                else{
                    q -> setRChild(p);
                    break;
                }
            }
        }
    }
}

BSTree::~BSTree() = default;

int BSTree::getNum()
{
    return num;
}

BSTreeNode* BSTree::getRoot()
{
    return root;
}

void BSTree::setNum(int n)
{
    num = n;
}

void BSTree::setRoot(BSTreeNode* r)
{
    root = r;
}

void printTemp(BSTreeNode* node, string& result)
{
    int num = node -> getData();
    result += to_string(num);
    result += ' ';
    if(node -> getLChild()){
        printTemp(node -> getLChild(), result);
    }
    if(node -> getRChild()){
        printTemp(node -> getRChild(), result);
    }
}

string BSTree::printTree()
{
    string result = "";
    printTemp(root, result);
    return result;
}

bool BSTree::searchNode(int val)
{
    BSTreeNode* q = root;
        while(q){
            if(val == q -> getData()){
                return true;
            }
            else if(val < q -> getData()){
                q = q -> getLChild();
            }
            else{
                q = q -> getRChild();
            }
        }
    return false;
}


bool BSTree::addNode(int val)
{
    BSTreeNode* node = new BSTreeNode;
    node -> setData(val);
    BSTreeNode* q = root;
    while(q){
        if(val == q -> getData()){
            return false;
        }
        else if(val < q -> getData()){
            if(q -> getLChild())
                q = q -> getLChild();
            else{ 
                q -> setLChild(node);
                return true;
            }
        }
        else{
            if(q -> getRChild())
                q = q -> getRChild();
            else{ 
                q -> setRChild(node);
                return true;
            }
        }
    }
    return true;
}

bool BSTree::deleteNode(int val)
{
    BSTreeNode* q = root;
    BSTreeNode* parent = root;
    bool left = 1;
    while(q){
        if(val == q -> getData()){
            break;
        }
        else if(val < q -> getData()){
            parent = q;
            q = q -> getLChild();
            left = 1;
        }
        else{
            parent = q;
            q = q -> getRChild();
            left = 0;
        }
    }
    if(!q){
        return false;
    }
    if(!q -> getLChild() && !q -> getRChild()){
        if(left == 1)
            parent -> setLChild(NULL);
        else if(left == 0)
            parent -> setRChild(NULL);
        delete q;
        return true;
    }
    else if(q -> getLChild() && q -> getRChild()){
        BSTreeNode* former = q -> getLChild();
        BSTreeNode* formerparent = q;
        if(!former -> getRChild()){
            q -> setData(former -> getData());
            q -> setLChild(NULL);
            delete former;
            return true;
        }
        while(former -> getRChild()){
            formerparent = former;
            former = former -> getRChild();
        }
        q -> setData(former -> getData());
        if(!former -> getLChild()){
            formerparent -> setRChild(NULL);
            delete former;
            return true;
        }
        else{
            formerparent -> setRChild(former -> getLChild());
            delete former;
            return true;
        }   
        return true;
    }
    else{
        if(left == 1){
            parent -> setLChild((q -> getLChild()) ? q -> getLChild() : q -> getRChild());
        }
        else{
            parent -> setRChild((q -> getLChild()) ? q -> getLChild() : q -> getRChild());
        }
        delete q;
        return true;
    }
}
